package com.demo47_全排列2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution_used数组去重 {
    public static void main(String[] args) {
        int[] ints={3,3,0,3};
        Arrays.sort(ints);
        List<List<Integer>> list = permuteUnique(ints);
        for (List<Integer> item : list) {
            System.out.println(item);
        }
    }
    public static List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> arrayList = new ArrayList<>();
        ArrayList<Integer> path = new ArrayList<>();
        int[] used = new int[nums.length];
        Arrays.fill(used,0);

        dfs(nums,path,arrayList,used);

        return arrayList;
    }

    private static void dfs(int[] nums, ArrayList<Integer> path, List<List<Integer>> arrayList, int[] used) {
        // 边界条件
        if (path.size() == nums.length){
            // 收集结果
            ArrayList<Integer> temp = new ArrayList<>();
            for (Integer item : path) {
                temp.add(item);
            }

            arrayList.add(temp);
            return;
        }

        // 横向遍历 + 纵向递归
        for (int i = 0; i < nums.length; i++) {
            // 去重的逻辑: 树层上去重~
            if (i>0&&used[i-1]==0&&nums[i]==nums[i-1]){
                continue;
            }
            if (used[i]==0) {
                // 处理当前元素
                path.add(nums[i] );
                used[i]=1;
                // 递归
                dfs(nums,path,arrayList,used);
                // 回溯
                path.remove(path.size()-1);
                used[i]=0;
            }

        }

    }

}
